import java.util.*;
import java.io.*;

public class Lab2
{
	public static void main(String[] args)
	{
		new Lab2(args);
	}

	public Lab2(String[] args)
	{
		if(args.length != 1)
		{
			System.err.println("Usage `java Lab2 FILE`");
			return;
		}

		// Initiate algorithms
		PathAlg greedy1 = new GreedyAlgorithmPrimm();
		PathAlg greedy2 = new GreedyAlgorithmKruskal();
		PathAlg exhaustive = new ExhaustiveAlgorithm();
		
		// Set up graphs
		greedy1.buildGraph(args[0]);
		greedy2.buildGraph(args[0]);
		exhaustive.buildGraph(args[0]);

		// Run algorithms and print
		long timeGreedy1 = greedy1.runAlgorithmTimed();
		printAlgorithm(greedy1);
		
		long timeGreedy2 = greedy2.runAlgorithmTimed();
		printAlgorithm(greedy2);
		
		long timeExhaustive = exhaustive.runAlgorithmTimed();
		printAlgorithm(exhaustive);
	}

	private void printAlgorithm(PathAlg alg)
	{
		System.out.println("=== Running " + alg.getName() + " === ");
		System.out.print("Min. EL: "
			+ alg.getExpectedLatency() + "\nPath: ");
		for(int i : alg.getPath())
		{
			System.out.print((i+1) + " ");
		}

		System.out.println("\nExecution time in ms: " + alg.getTime());
		System.out.println();
	}
	
	
    // Base class for all algorithms
	public abstract class PathAlg {
    	// Result
    	protected float expectedLatency = -1;
    	protected int[] path = null;
    	protected long time = -1;

    	// Graph
    	protected float[] probabilities  = null;
    	protected int[][] costs = null;

    	public abstract void runAlgorithm();
    	public abstract String getName();

    	public long runAlgorithmTimed()
    	{
    		long t = Calendar.getInstance().getTimeInMillis();
    		runAlgorithm();
    		this.time = Calendar.getInstance().getTimeInMillis() - t;

    		return this.time;
    	}
    	
    	public void buildGraph(String inputFile)
    	{
    		// Parse file and set up graph
    		BufferedReader in;

    		try
    		{
    			in = new BufferedReader(new FileReader(inputFile));
    		}
    		catch(FileNotFoundException ex)
    		{
    			System.err.println("File \"" + inputFile + "\" not found.");
    			return;
    		}
    		
    		String line;
    		try
    		{
    			int i = 0;
    			int numNodes = 0;
    			while((line = in.readLine()) != null)
    			{
    				// First line should contain our array lengths
    				if(i == 0)
    				{
    					numNodes = Integer.parseInt(line);
    					costs = new int[numNodes][numNodes];
    					probabilities = new float[numNodes];

    					path = new int[numNodes];
    					// Always visit first node first
    					this.path[0] = 0;
    				}
    				// The next numNodes lines should contain probabilities
    				else if(i <= numNodes)
    				{
    					probabilities[i-1] = Float.parseFloat(line);
    				}
    				// And the rest should hold our cost matrix
    				else
    				{
    					String[] nums = line.split(" ");
    					for(int j=0; j<nums.length; ++j)
    					{
    						costs[i-1-numNodes][j] = Integer.parseInt(nums[j]);
    					}
    				}
    				i = i + 1;
    			}
    		}
    		catch(IOException ex)
    		{
    			System.err.println("Error when reading file.");
    		}
    	}

    	public int[] getPath()
    	{
    		if(this.path == null)
    		{
    			throw new IllegalStateException("Algorithm has not been run");
    		}

    		return this.path;
    	}

    	protected float calculateExpectedLatency(int[] path)
    	{
    		float sum = 0;
    		int pathCost = 0;
    		int lastNode = 0;
    		for(int v : path)
    		{
    			// Do not need to calculate first step 
    			if(v == 0)
    			{
    				continue;
    			}

    			pathCost += costs[lastNode][v];
    			sum += probabilities[v]*pathCost;

    			lastNode = v;
    		}

    		return sum;
    	}

    	public float getExpectedLatency()
    	{
    		if(this.path == null)
    		{
    			throw new IllegalStateException("Algorithm has not been run");
    		}

    		if(this.expectedLatency < 0)
    		{
    			this.expectedLatency = calculateExpectedLatency(this.path);
    		}

    		return this.expectedLatency;
    	}

    	public long getTime()
    	{
    		if(this.time < 0)
    			throw new IllegalStateException("Timed algorithm not run.");

    		return this.time;
    	}
    }
    
    
    // Exhaustive algorithm
    public class ExhaustiveAlgorithm extends PathAlg {
    	public void runAlgorithm() {
    		HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
    		visited.put(0, true);
    		AlgRet newPath = visitRest(visited, new int[] { 0 });
    		this.expectedLatency = newPath.expectedLatency;
    		this.path = newPath.path;
    	}

    	private AlgRet visitRest(HashMap<Integer, Boolean> visited, int[] prePath) {
    		AlgRet ret = null;

    		for(int i=0; i<costs.length; i++) {
    			if(visited.get(i) == null) {
    				// The new, resulting path, after arriving at this node
    				int[] pathToHere = new int[prePath.length + 1];
    				// Copy previous nodes
    				System.arraycopy(prePath, 0, pathToHere, 0, prePath.length);
    				// Add current node last
    				pathToHere[pathToHere.length - 1] = i;

    				// Only leaf nodes calculate path length
    				if(pathToHere.length == path.length) {
    					return new AlgRet(calculateExpectedLatency(pathToHere), pathToHere);
    				}
    				else {
    					// Mark current node as visited
    					visited.put(i, true);

    					// Get the shortest path from this node
    					AlgRet newPath = visitRest(visited, pathToHere);

    					// If this is the shortest, or the first, update return value
    					if(ret == null || newPath.expectedLatency < ret.expectedLatency)
    						ret = newPath;

    					// We're leaving the node
    					visited.remove(i);
    				}
    				
    			}
    		}
    		return ret;
    	}
    	
    	public String getName() {
    	    return "Exhaustive";
        }

    	private class AlgRet {
    		public float expectedLatency; 
    		public int[] path;
    		public AlgRet(float el, int[] p) { expectedLatency = el; path = p; }
    	}
    }
    
    
    // 1st Greedy algorithm - Kruskal
    public class GreedyAlgorithmKruskal extends PathAlg {
    	public void runAlgorithm() {
    		// List to store the final tree
    		LinkedList<Edge> tree = new LinkedList<Edge>();

    		// List to store the final path, to be returned from the algorithm
    		LinkedList<Integer> path = new LinkedList<Integer>();

    		// For our particular case, we also need to keep track of the number 
    		// of outgoing edges from every node, since we want a path, and not
    		// a general path. Also, we can use this to originate the path from
    		// node 1.
    		HashMap<Integer, Integer> edgeCount = new HashMap<Integer, Integer>();

    		// Set up queue
    		PriorityQueue<Edge> pQueue = new PriorityQueue<Edge>();

    		for(int row=0; row<costs.length; ++row)
    		{
    			for(int cell=row+1; cell<costs[row].length; ++cell)
    			{
    				pQueue.offer(new Edge(row, cell));
    			}
    		}

    		// Create Union-Find
    		UnionFind uf = new UnionFind(costs.length);

    		// Start Kruskal's!!
    		while(tree.size() < costs.length-1)
    		{
    			Edge e = pQueue.poll();
    			int[] nodes = e.getNodes();

    			/*	Here, we divert from running a pure Kruskal.		*/
    			final boolean node0HasAny = edgeCount.get(nodes[0]) != null;
    			final boolean node1HasAny = edgeCount.get(nodes[1]) != null;

    			// Make sure no node has more than 2 outgoing edges
    			if(node0HasAny && edgeCount.get(nodes[0]) > 1)
    				continue;
    			else if(node1HasAny &&edgeCount.get(nodes[1]) > 1)
    				continue;
    			// Make sure the start node only has 1 outgoing edge
    			else if(nodes[0] == 0 && node0HasAny)
    				continue;
    			else if(nodes[1] == 0 && node1HasAny)
    				continue;


    			/*	Back to kruskal. 									*/
    			if(!uf.sameSet(nodes[0], nodes[1]))
    			{
    				uf.setUnion(nodes[0], nodes[1]);
    				tree.add(e);

    				if(node0HasAny)
    					edgeCount.put(nodes[0], 2);
    				else
    					edgeCount.put(nodes[0], 1);

    				if(node1HasAny)
    					edgeCount.put(nodes[1], 2);
    				else
    					edgeCount.put(nodes[1], 1);
    			}
    		}

    		// Construct path
    		path.add(0);
    		while(tree.size() > 0)
    		{
    			int last = path.get(path.size()-1);
    			for(Edge e : tree)
    			{
    				int[] nodes = e.getNodes();
    				if(nodes[0] == last)
    				{
    					tree.remove(e);
    					path.add(nodes[1]);
    					break;
    				}
    				else if(nodes[1] == last)
    				{
    					tree.remove(e);
    					path.add(nodes[0]);
    					break;
    				}
    			}
    		}

    		Integer[] p = path.toArray(new Integer[path.size()]);
    		this.path = new int[path.size()];
    		for(int i=0; i<p.length; ++i)
    			this.path[i] = p[i];
    	}
    	
    	public String getName() {
    	    return "Kruskal";
        }

    	/**
    	 *	Simple weighted undirected edge representation
    	 */
    	private class Edge implements Comparable<Edge> {
    		private int n1, n2;
    		private double w;

    		public Edge(int n1, int n2)
    		{
    			this.n1 = n1;
    			this.n2 = n2;
    			this.w  = costs[n1][n2] / (0.5 * probabilities[n1] * probabilities[n2]);
    		}
    		public int[] getNodes() { return new int[]{n1,n2}; }
    		public int compareTo(Edge other)
    		{
    			double diff = this.w - other.w;

    			if(diff == 0)
    				return 0;
    			else if(diff < 0)
    				return -1;
    			else
    				return 1;
    		}
    	}

    	
    	/**
    	 * Union-Find datastructure.
    	 */
    	private class UnionFind {
    		// Bottom-to-top tree structure
    		private class Record
    		{
    			int id;
    			int size;
    			Record parent = null;

    			public Record(int id)
    			{
    				this.id = id;
    			}
    			public int getId()
    			{
    				return this.id;
    			}

    			public void addToSize(int size)
    			{
    				this.size += size;
    			}
    			public int getSize()
    			{
    				return this.size;
    			}

    			public void setParent(Record parent)
    			{
    				this.parent = parent;
    				parent.addToSize(this.size);
    			}
    			public Record getParent()
    			{
    				return this.parent;
    			}

    			public boolean equals(Object other)
    			{
    				if(other == null || getClass() != other.getClass() ) {
    					return false;
    				}
    				else {
    					Record o = (Record) other;
    					return id == o.getId();
    				}
    			}
    		}

    		private ArrayList<Record> records = new ArrayList<Record>();
    		private HashMap<Integer, Record> recordMap = new HashMap<Integer, Record>();
    		
    		public UnionFind(int count)
    		{
    			for(int i=0; i<count; ++i)
    			{
    				Record r = new Record(i);
    				records.add(r);
    				recordMap.put(i, r);
    			}
    		}

    		public void setUnion(int x, int y)
    		{
    			setUnion(recordMap.get(x), recordMap.get(y));
    		}
    		public void setUnion(Record x, Record y)
    		{
    			Record xRoot = find(x);
    			Record yRoot = find(y);

    			if(xRoot.getSize() > yRoot.getSize())
    			{
    				yRoot.setParent(xRoot);
    			}
    			else
    			{
    				xRoot.setParent(yRoot);
    			}
    		}

    		public Record find(Record rec)
    		{
    			if(rec.getParent() == null)
    			{
    				return rec;
    			}
    			else
    			{
    				rec.setParent(find(rec.getParent()));
    				return rec.getParent();
    			}
    		}
    		
    		public boolean sameSet(int x, int y)
    		{
    			return sameSet(recordMap.get(x), recordMap.get(y));
    		}
    		public boolean sameSet(Record x, Record y)
    		{
                    return find(x).equals(find(y));
            }
    	}
    }
    
    // 2nd Greedy algorithm - Primm
    public class GreedyAlgorithmPrimm extends PathAlg {
        private List<Node> nodes;
        private List<Node> notTaken;
        private Node tail;

    	public void runAlgorithm() {
    	    init();

      	    int pathCost = 0;   // increments in every iteration
            while(notTaken.size() > 0) {
                // Find closest and remove it from set 'notTaken'
                Node closest = null;
                for(Node n : notTaken) {
                    if(closest == null || (n.cost/probabilities[n.id]) < (closest.cost/probabilities[closest.id]))
                        closest = n;
                }

                // Add EL cost and node in path
                closest.pathPosition = tail.pathPosition + 1;
                path[tail.pathPosition + 1] = closest.id;
                pathCost += costs[tail.id][closest.id];
                expectedLatency += pathCost * probabilities[closest.id];
                tail = closest; // keep track of tail node
                
                // Update notTaken set
                notTaken.remove(closest);   // remove just taken node
                for(Node n : notTaken) {    // update costs
                    n.cost = pathCost + costs[tail.id][n.id];
                }
            }
    	}

    	private void init() {
            int nodeCount = costs.length;
    	    notTaken = new ArrayList<Node>(nodeCount);
    	    nodes = new ArrayList<Node>(nodeCount);
    	    expectedLatency = 0;
    	
    		// Create nodes
    		for(int i = 0; i < nodeCount; i++) {
    		    Node n = new Node(i, costs[0][i]);
    		    nodes.add(i,n);
    		}

            // Initialize path and EL which we will greedily build up		
            tail = nodes.get(0);
            tail.pathPosition = 0;
            path[0] = 0;

    		// Init notTaken list to contain all but start node
    		for(int i = 1; i < nodeCount; i++) {
    		    notTaken.add(nodes.get(i));
    		}
    	}
    	
    	public String getName() {
    	    return "Primm";
        }
    	
    	// Class representing a node
    	private class Node {
    	    public int id, cost, pathPosition;
    	    

    	   	public Node(int id, int cost) {
        	    this.id = id;
        	    this.cost = cost;
        	    this.pathPosition = -1;
        	}
    	}
    }
}
